home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 2: CDPD 1 / Almathera Ten on Ten - Disc 2: CDPD 1.iso / pd / 176-200 / 197 / stevie / regexp.c < prev    next >
C/C++ Source or Header  |  1995-03-13  |  32KB  |  1,302 lines
  1. /*
  2.  * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
  3.  *
  4.  * This is NOT the original regular expression code as written by
  5.  * Henry Spencer. This code has been modified specifically for use
  6.  * with the STEVIE editor, and should not be used apart from compiling
  7.  * STEVIE. If you want a good regular expression library, get the
  8.  * original code. The copyright notice that follows is from the
  9.  * original.
  10.  *
  11.  * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
  12.  *
  13.  *
  14.  * regcomp and regexec -- regsub and regerror are elsewhere
  15.  *
  16.  *    Copyright (c) 1986 by University of Toronto.
  17.  *    Written by Henry Spencer.  Not derived from licensed software.
  18.  *
  19.  *    Permission is granted to anyone to use this software for any
  20.  *    purpose on any computer system, and to redistribute it freely,
  21.  *    subject to the following restrictions:
  22.  *
  23.  *    1. The author is not responsible for the consequences of use of
  24.  *        this software, no matter how awful, even if they arise
  25.  *        from defects in it.
  26.  *
  27.  *    2. The origin of this software must not be misrepresented, either
  28.  *        by explicit claim or by omission.
  29.  *
  30.  *    3. Altered versions must be plainly marked as such, and must not
  31.  *        be misrepresented as being the original software.
  32.  *
  33.  * Beware that some of this code is subtly aware of the way operator
  34.  * precedence is structured in regular expressions.  Serious changes in
  35.  * regular-expression syntax might require a total rethink.
  36.  *
  37.  * $Log:    regexp.c,v $
  38.  * Revision 1.2  88/04/28  08:09:45  tony
  39.  * First modification of the regexp library. Added an external variable
  40.  * 'reg_ic' which can be set to indicate that case should be ignored.
  41.  * Added a new parameter to regexec() to indicate that the given string
  42.  * comes from the beginning of a line and is thus eligible to match
  43.  * 'beginning-of-line'.
  44.  * 
  45.  */
  46. #include "env.h"
  47.  
  48. #ifdef    MEGAMAX
  49. overlay "regexp"
  50. #endif
  51.  
  52. #include <stdio.h>
  53. #include "regexp.h"
  54. #include "regmagic.h"
  55.  
  56. /*
  57.  * The "internal use only" fields in regexp.h are present to pass info from
  58.  * compile to execute that permits the execute phase to run lots faster on
  59.  * simple cases.  They are:
  60.  *
  61.  * regstart    char that must begin a match; '\0' if none obvious
  62.  * reganch    is the match anchored (at beginning-of-line only)?
  63.  * regmust    string (pointer into program) that match must include, or NULL
  64.  * regmlen    length of regmust string
  65.  *
  66.  * Regstart and reganch permit very fast decisions on suitable starting points
  67.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  68.  * of lines that cannot possibly match.  The regmust tests are costly enough
  69.  * that regcomp() supplies a regmust only if the r.e. contains something
  70.  * potentially expensive (at present, the only such thing detected is * or +
  71.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  72.  * supplied because the test in regexec() needs it and regcomp() is computing
  73.  * it anyway.
  74.  */
  75.  
  76. /*
  77.  * Structure for regexp "program".  This is essentially a linear encoding
  78.  * of a nondeterministic finite-state machine (aka syntax charts or
  79.  * "railroad normal form" in parsing technology).  Each node is an opcode
  80.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  81.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  82.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  83.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  84.  * opposed to a collection of them) is never concatenated with anything
  85.  * because of operator precedence.)  The operand of some types of node is
  86.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  87.  * particular, the operand of a BRANCH node is the first node of the branch.
  88.  * (NB this is *not* a tree structure:  the tail of the branch connects
  89.  * to the thing following the set of BRANCHes.)  The opcodes are:
  90.  */
  91.  
  92. /* definition    number    opnd?    meaning */
  93. #define    END    0        /* no    End of program. */
  94. #define    BOL    1        /* no    Match "" at beginning of line. */
  95. #define    EOL    2        /* no    Match "" at end of line. */
  96. #define    ANY    3        /* no    Match any one character. */
  97. #define    ANYOF    4        /* str    Match any character in this string. */
  98. #define    ANYBUT    5        /* str    Match any character not in this
  99.                  * string. */
  100. #define    BRANCH    6        /* node    Match this alternative, or the
  101.                  * next... */
  102. #define    BACK    7        /* no    Match "", "next" ptr points backward. */
  103. #define    EXACTLY    8        /* str    Match this string. */
  104. #define    NOTHING    9        /* no    Match empty string. */
  105. #define    STAR    10        /* node    Match this (simple) thing 0 or more
  106.                  * times. */
  107. #define    PLUS    11        /* node    Match this (simple) thing 1 or more
  108.                  * times. */
  109. #define    OPEN    20        /* no    Mark this point in input as start of
  110.                  * #n. */
  111.  /* OPEN+1 is number 1, etc. */
  112. #define    CLOSE    30        /* no    Analogous to OPEN. */
  113.  
  114. /*
  115.  * Opcode notes:
  116.  *
  117.  * BRANCH    The set of branches constituting a single choice are hooked
  118.  *        together with their "next" pointers, since precedence prevents
  119.  *        anything being concatenated to any individual branch.  The
  120.  *        "next" pointer of the last BRANCH in a choice points to the
  121.  *        thing following the whole choice.  This is also where the
  122.  *        final "next" pointer of each individual branch points; each
  123.  *        branch starts with the operand node of a BRANCH node.
  124.  *
  125.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  126.  *        exists to make loop structures possible.
  127.  *
  128.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  129.  *        BRANCH structures using BACK.  Simple cases (one character
  130.  *        per match) are implemented with STAR and PLUS for speed
  131.  *        and to minimize recursive plunges.
  132.  *
  133.  * OPEN,CLOSE    ...are numbered at compile time.
  134.  */
  135.  
  136. /*
  137.  * A node is one char of opcode followed by two chars of "next" pointer.
  138.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  139.  * value is a positive offset from the opcode of the node containing it.
  140.  * An operand, if any, simply follows the node.  (Note that much of the
  141.  * code generation knows about this implicit relationship.)
  142.  *
  143.  * Using two bytes for the "next" pointer is vast overkill for most things,
  144.  * but allows patterns to get big without disasters.
  145.  */
  146. #define    OP(p)    (*(p))
  147. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  148. #define    OPERAND(p)    ((p) + 3)
  149.  
  150. /*
  151.  * See regmagic.h for one further detail of program structure.
  152.  */
  153.  
  154.  
  155. /*
  156.  * Utility definitions.
  157.  */
  158. #ifndef CHARBITS
  159. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  160. #else
  161. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  162. #endif
  163.  
  164. #define    FAIL(m)    { regerror(m); return(NULL); }
  165. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  166. #define    META    "^$.[()|?+*\\"
  167.  
  168. /*
  169.  * Flags to be passed up and down.
  170.  */
  171. #define    HASWIDTH    01    /* Known never to match null string. */
  172. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  173. #define    SPSTART        04    /* Starts with * or +. */
  174. #define    WORST        0    /* Worst case. */
  175.  
  176. #ifndef    ORIGINAL
  177. /*
  178.  * The following supports the ability to ignore case in searches.
  179.  */
  180.  
  181. #include <ctype.h>
  182.  
  183. int             reg_ic = 0;    /* set by callers to ignore case */
  184.  
  185. /*
  186.  * mkup - convert to upper case IF we're doing caseless compares
  187.  */
  188. #define    mkup(c)        ((islower(c) && reg_ic) ? toupper(c) : (c))
  189.  
  190. #endif
  191.  
  192. /*
  193.  * Global work variables for regcomp().
  194.  */
  195. static char    *regparse;    /* Input-scan pointer. */
  196. static int      regnpar;    /* () count. */
  197. static char     regdummy;
  198. static char    *regcode;    /* Code-emit pointer; ®dummy = don't. */
  199. static long     regsize;    /* Code size. */
  200.  
  201. /*
  202.  * Forward declarations for regcomp()'s friends.
  203.  */
  204. #ifndef STATIC
  205. #define    STATIC    static
  206. #endif
  207. STATIC char    *reg();
  208. STATIC char    *regbranch();
  209. STATIC char    *regpiece();
  210. STATIC char    *regatom();
  211. STATIC char    *regnode();
  212. STATIC char    *regnext();
  213. STATIC void     regc();
  214. STATIC void     reginsert();
  215. STATIC void     regtail();
  216. STATIC void     regoptail();
  217. #ifdef STRCSPN
  218. STATIC int      strcspn();
  219. #endif
  220.  
  221. /*
  222.  - regcomp - compile a regular expression into internal code
  223.  *
  224.  * We can't allocate space until we know how big the compiled form will be,
  225.  * but we can't compile it (and thus know how big it is) until we've got a
  226.  * place to put the code.  So we cheat:  we compile it twice, once with code
  227.  * generation turned off and size counting turned on, and once "for real".
  228.  * This also means that we don't allocate space until we are sure that the
  229.  * thing really will compile successfully, and we never have to move the
  230.  * code and thus invalidate pointers into it.  (Note that it has to be in
  231.  * one piece because free() must be able to free it all.)
  232.  *
  233.  * Beware that the optimization-preparation code in here knows about some
  234.  * of the structure of the compiled regexp.
  235.  */
  236. regexp         *
  237. regcomp(exp)
  238.     char           *exp;
  239. {
  240.     register regexp *r;
  241.     register char  *scan;
  242.     register char  *longest;
  243.     register int    len;
  244.     int             flags;
  245. /*  extern char    *malloc();*/
  246.     extern char    *alloc();
  247.  
  248.     if (exp == NULL)
  249.     FAIL("NULL argument");
  250.  
  251.     /* First pass: determine size, legality. */
  252.     regparse = exp;
  253.     regnpar = 1;
  254.     regsize = 0L;
  255.     regcode = ®dummy;
  256.     regc(MAGIC);
  257.     if (reg(0, &flags) == NULL)
  258.     return (NULL);
  259.  
  260.     /* Small enough for pointer-storage convention? */
  261.     if (regsize >= 32767L)    /* Probably could be 65535L. */
  262.     FAIL("regexp too big");
  263.  
  264.     /* Allocate space. */
  265. /*  r = (regexp *) malloc((unsigned) (sizeof(regexp) + regsize));*/
  266.     r = (regexp *) alloc((unsigned) (sizeof(regexp) + regsize));
  267.     if (r == NULL)
  268.     FAIL("out of space");
  269.  
  270.     /* Second pass: emit code. */
  271.     regparse = exp;
  272.     regnpar = 1;
  273.     regcode = r->program;
  274.     regc(MAGIC);
  275.     if (reg(0, &flags) == NULL)
  276.     return (NULL);
  277.  
  278.     /* Dig out information for optimizations. */
  279.     r->regstart = '\0';        /* Worst-case defaults. */
  280.     r->reganch = 0;
  281.     r->regmust = NULL;
  282.     r->regmlen = 0;
  283.     scan = r->program + 1;    /* First BRANCH. */
  284.     if (OP(regnext(scan)) == END) {    /* Only one top-level choice. */
  285.     scan = OPERAND(scan);
  286.  
  287.     /* Starting-point info. */
  288.     if (OP(scan) == EXACTLY)
  289.         r->regstart = *OPERAND(scan);
  290.     else if (OP(scan) == BOL)
  291.         r->reganch++;
  292.  
  293.     /*
  294.      * If there's something expensive in the r.e., find the longest
  295.      * literal string that must appear and make it the regmust.  Resolve
  296.      * ties in favor of later strings, since the regstart check works
  297.      * with the beginning of the r.e. and avoiding duplication
  298.      * strengthens checking.  Not a strong reason, but sufficient in the
  299.      * absence of others. 
  300.      */
  301.     if (flags & SPSTART) {
  302.         longest = NULL;
  303.         len = 0;
  304.         for (; scan != NULL; scan = regnext(scan))
  305.         if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  306.             longest = OPERAND(scan);
  307.             len = strlen(OPERAND(scan));
  308.         }
  309.         r->regmust = longest;
  310.         r->regmlen = len;
  311.     }
  312.     }
  313.     return (r);
  314. }
  315.  
  316. /*
  317.  - reg - regular expression, i.e. main body or parenthesized thing
  318.  *
  319.  * Caller must absorb opening parenthesis.
  320.  *
  321.  * Combining parenthesis handling with the base level of regular expression
  322.  * is a trifle forced, but the need to tie the tails of the branches to what
  323.  * follows makes it hard to avoid.
  324.  */
  325. static char    *
  326. reg(paren, flagp)
  327.     int             paren;    /* Parenthesized? */
  328.     int            *flagp;
  329. {
  330.     register char  *ret;
  331.     register char  *br;
  332.     register char  *ender;
  333.     register int    parno;
  334.     int             flags;
  335.  
  336.     *flagp = HASWIDTH;        /* Tentatively. */
  337.  
  338.     /* Make an OPEN node, if parenthesized. */
  339.     if (paren) {
  340.     if (regnpar >= NSUBEXP)
  341.         FAIL("too many ()");
  342.     parno = regnpar;
  343.     regnpar++;
  344.     ret = regnode(OPEN + parno);
  345.     } else
  346.     ret = NULL;
  347.  
  348.     /* Pick up the branches, linking them together. */
  349.     br = regbranch(&flags);
  350.     if (br == NULL)
  351.     return (NULL);
  352.     if (ret != NULL)
  353.     regtail(ret, br);    /* OPEN -> first. */
  354.     else
  355.     ret = br;
  356.     if (!(flags & HASWIDTH))
  357.     *flagp &= ~HASWIDTH;
  358.     *flagp |= flags & SPSTART;
  359.     while (*regparse == '|') {
  360.     regparse++;
  361.     br = regbranch(&flags);
  362.     if (br == NULL)
  363.         return (NULL);
  364.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  365.     if (!(flags & HASWIDTH))
  366.         *flagp &= ~HASWIDTH;
  367.     *flagp |= flags & SPSTART;
  368.     }
  369.  
  370.     /* Make a closing node, and hook it on the end. */
  371.     ender = regnode((paren) ? CLOSE + parno : END);
  372.     regtail(ret, ender);
  373.  
  374.     /* Hook the tails of the branches to the closing node. */
  375.     for (br = ret; br != NULL; br = regnext(br))
  376.     regoptail(br, ender);
  377.  
  378.     /* Check for proper termination. */
  379.     if (paren && *regparse++ != ')') {
  380.     FAIL("unmatched ()");
  381.     } else if (!paren && *regparse != '\0') {
  382.     if (*regparse == ')') {
  383.         FAIL("unmatched ()");
  384.     } else
  385.         FAIL("junk on end");/* "Can't happen". */
  386.     /* NOTREACHED */
  387.     }
  388.     return (ret);
  389. }
  390.  
  391. /*
  392.  - regbranch - one alternative of an | operator
  393.  *
  394.  * Implements the concatenation operator.
  395.  */
  396. static char    *
  397. regbranch(flagp)
  398.     int            *flagp;
  399. {
  400.     register char  *ret;
  401.     register char  *chain;
  402.     register char  *latest;
  403.     int             flags;
  404.  
  405.     *flagp = WORST;        /* Tentatively. */
  406.  
  407.     ret = regnode(BRANCH);
  408.     chain = NULL;
  409.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  410.     latest = regpiece(&flags);
  411.     if (latest == NULL)
  412.         return (NULL);
  413.     *flagp |= flags & HASWIDTH;
  414.     if (chain == NULL)    /* First piece. */
  415.         *flagp |= flags & SPSTART;
  416.     else
  417.         regtail(chain, latest);
  418.     chain = latest;
  419.     }
  420.     if (chain == NULL)        /* Loop ran zero times. */
  421.     (void) regnode(NOTHING);
  422.  
  423.     return (ret);
  424. }
  425.  
  426. /*
  427.  - regpiece - something followed by possible [*+?]
  428.  *
  429.  * Note that the branching code sequences used for ? and the general cases
  430.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  431.  * both the endmarker for their branch list and the body of the last branch.
  432.  * It might seem that this node could be dispensed with entirely, but the
  433.  * endmarker role is not redundant.
  434.  */
  435. static char    *
  436. regpiece(flagp)
  437.     int            *flagp;
  438. {
  439.     register char  *ret;
  440.     register char   op;
  441.     register char  *next;
  442.     int             flags;
  443.  
  444.     ret = regatom(&flags);
  445.     if (ret == NULL)
  446.     return (NULL);
  447.  
  448.     op = *regparse;
  449.     if (!ISMULT(op)) {
  450.     *flagp = flags;
  451.     return (ret);
  452.     }
  453.     if (!(flags & HASWIDTH) && op != '?')
  454.     FAIL("*+ operand could be empty");
  455.     *flagp = (op != '+') ? (WORST | SPSTART) : (WORST | HASWIDTH);
  456.  
  457.     if (op == '*' && (flags & SIMPLE))
  458.     reginsert(STAR, ret);
  459.     else if (op == '*') {
  460.     /* Emit x* as (x&|), where & means "self". */
  461.     reginsert(BRANCH, ret);    /* Either x */
  462.     regoptail(ret, regnode(BACK));    /* and loop */
  463.     regoptail(ret, ret);    /* back */
  464.     regtail(ret, regnode(BRANCH));    /* or */
  465.     regtail(ret, regnode(NOTHING));    /* null. */
  466.     } else if (op == '+' && (flags & SIMPLE))
  467.     reginsert(PLUS, ret);
  468.     else if (op == '+') {
  469.     /* Emit x+ as x(&|), where & means "self". */
  470.     next = regnode(BRANCH);    /* Either */
  471.     regtail(ret, next);
  472.     regtail(regnode(BACK), ret);    /* loop back */
  473.     regtail(next, regnode(BRANCH));    /* or */
  474.     regtail(ret, regnode(NOTHING));    /* null. */
  475.     } else if (op == '?') {
  476.     /* Emit x? as (x|) */
  477.     reginsert(BRANCH, ret);    /* Either x */
  478.     regtail(ret, regnode(BRANCH));    /* or */
  479.     next = regnode(NOTHING);/* null. */
  480.     regtail(ret, next);
  481.     regoptail(ret, next);
  482.     }
  483.     regparse++;
  484.     if (ISMULT(*regparse))
  485.     FAIL("nested *?+");
  486.  
  487.     return (ret);
  488. }
  489.  
  490. /*
  491.  - regatom - the lowest level
  492.  *
  493.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  494.  * it can turn them into a single node, which is smaller to store and
  495.  * faster to run.  Backslashed characters are exceptions, each becoming a
  496.  * separate node; the code is simpler that way and it's not worth fixing.
  497.  */
  498. static char    *
  499. regatom(flagp)
  500.     int            *flagp;
  501. {
  502.     register char  *ret;
  503.     int             flags;
  504.  
  505.     *flagp = WORST;        /* Tentatively. */
  506.  
  507.     switch (*regparse++) {
  508.       case '^':
  509.     ret = regnode(BOL);
  510.     break;
  511.       case '$':
  512.     ret = regnode(EOL);
  513.     break;
  514.       case '.':
  515.     ret = regnode(ANY);
  516.     *flagp |= HASWIDTH | SIMPLE;
  517.     break;
  518.       case '[':{
  519.         register int    class;
  520.         register int    classend;
  521.  
  522.         if (*regparse == '^') {    /* Complement of range. */
  523.         ret = regnode(ANYBUT);
  524.         regparse++;
  525.         } else
  526.         ret = regnode(ANYOF);
  527.         if (*regparse == ']' || *regparse == '-')
  528.         regc(*regparse++);
  529.         while (*regparse != '\0' && *regparse != ']') {
  530.         if (*regparse == '-') {
  531.             regparse++;
  532.             if (*regparse == ']' || *regparse == '\0')
  533.             regc('-');
  534.             else {
  535.             class = UCHARAT(regparse - 2) + 1;
  536.             classend = UCHARAT(regparse);
  537.             if (class > classend + 1)
  538.                 FAIL("invalid [] range");
  539.             for (; class <= classend; class++)
  540.                 regc(class);
  541.             regparse++;
  542.             }
  543.         } else
  544.             regc(*regparse++);
  545.         }
  546.         regc('\0');
  547.         if (*regparse != ']')
  548.         FAIL("unmatched []");
  549.         regparse++;
  550.         *flagp |= HASWIDTH | SIMPLE;
  551.     }
  552.     break;
  553.       case '(':
  554.     ret = reg(1, &flags);
  555.     if (ret == NULL)
  556.         return (NULL);
  557.     *flagp |= flags & (HASWIDTH | SPSTART);
  558.     break;
  559.       case '\0':
  560.       case '|':
  561.       case ')':
  562.     FAIL("internal urp");    /* Supposed to be caught earlier. */
  563.     /* break; Not Reached */
  564.       case '?':
  565.       case '+':
  566.       case '*':
  567.     FAIL("?+* follows nothing");
  568.     /* break; Not Reached */
  569.       case '\\':
  570.     if (*regparse == '\0')
  571.         FAIL("trailing \\");
  572.     ret = regnode(EXACTLY);
  573.     regc(*regparse++);
  574.     regc('\0');
  575.     *flagp |= HASWIDTH | SIMPLE;
  576.     break;
  577.       default:{
  578.         register int    len;
  579.         register char   ender;
  580.  
  581.         regparse--;
  582.         len = strcspn(regparse, META);
  583.         if (len <= 0)
  584.         FAIL("internal disaster");
  585.         ender = *(regparse + len);
  586.         if (len > 1 && ISMULT(ender))
  587.         len--;        /* Back off clear of ?+* operand. */
  588.         *flagp |= HASWIDTH;
  589.         if (len == 1)
  590.         *flagp |= SIMPLE;
  591.         ret = regnode(EXACTLY);
  592.         while (len > 0) {
  593.         regc(*regparse++);
  594.         len--;
  595.         }
  596.         regc('\0');
  597.     }
  598.     break;
  599.     }
  600.  
  601.     return (ret);
  602. }
  603.  
  604. /*
  605.  - regnode - emit a node
  606.  */
  607. static char    *        /* Location. */
  608. regnode(op)
  609.     char            op;
  610. {
  611.     register char  *ret;
  612.     register char  *ptr;
  613.  
  614.     ret = regcode;
  615.     if (ret == ®dummy) {
  616.     regsize += 3;
  617.     return (ret);
  618.     }
  619.     ptr = ret;
  620.     *ptr++ = op;
  621.     *ptr++ = '\0';        /* Null "next" pointer. */
  622.     *ptr++ = '\0';
  623.     regcode = ptr;
  624.  
  625.     return (ret);
  626. }
  627.  
  628. /*
  629.  - regc - emit (if appropriate) a byte of code
  630.  */
  631. static void
  632. regc(b)
  633.     char            b;
  634. {
  635.     if (regcode != ®dummy)
  636.     *regcode++ = b;
  637.     else
  638.     regsize++;
  639. }
  640.  
  641. /*
  642.  - reginsert - insert an operator in front of already-emitted operand
  643.  *
  644.  * Means relocating the operand.
  645.  */
  646. static void
  647. reginsert(op, opnd)
  648.     char            op;
  649.     char           *opnd;
  650. {
  651.     register char  *src;
  652.     register char  *dst;
  653.     register char  *place;
  654.  
  655.     if (regcode == ®dummy) {
  656.     regsize += 3;
  657.     return;
  658.     }
  659.     src = regcode;
  660.     regcode += 3;
  661.     dst = regcode;
  662.     while (src > opnd)
  663.     *--dst = *--src;
  664.  
  665.     place = opnd;        /* Op node, where operand used to be. */
  666.     *place++ = op;
  667.     *place++ = '\0';
  668.     *place++ = '\0';
  669. }
  670.  
  671. /*
  672.  - regtail - set the next-pointer at the end of a node chain
  673.  */
  674. static void
  675. regtail(p, val)
  676.     char           *p;
  677.     char           *val;
  678. {
  679.     register char  *scan;
  680.     register char  *temp;
  681.     register int    offset;
  682.  
  683.     if (p == ®dummy)
  684.     return;
  685.  
  686.     /* Find last node. */
  687.     scan = p;
  688.     for (;;) {
  689.     temp = regnext(scan);
  690.     if (temp == NULL)
  691.         break;
  692.     scan = temp;
  693.     }
  694.  
  695.     if (OP(scan) == BACK)
  696.     offset = scan - val;
  697.     else
  698.     offset = val - scan;
  699.     *(scan + 1) = (char) ((offset >> 8) & 0377);
  700.     *(scan + 2) = (char) (offset & 0377);
  701. }
  702.  
  703. /*
  704.  - regoptail - regtail on operand of first argument; nop if operandless
  705.  */
  706. static void
  707. regoptail(p, val)
  708.     char           *p;
  709.     char           *val;
  710. {
  711.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  712.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  713.     return;
  714.     regtail(OPERAND(p), val);
  715. }
  716.  
  717. /*
  718.  * regexec and friends
  719.  */
  720.  
  721. /*
  722.  * Global work variables for regexec().
  723.  */
  724. static char    *reginput;    /* String-input pointer. */
  725. static char    *regbol;        /* Beginning of input, for ^ check. */
  726. static char   **regstartp;    /* Pointer to startp array. */
  727. static char   **regendp;    /* Ditto for endp. */
  728.  
  729. /*
  730.  * Forwards.
  731.  */
  732. STATIC int      regtry();
  733. STATIC int      regmatch();
  734. STATIC int      regrepeat();
  735.  
  736. #ifdef DEBUG
  737. int             regnarrate = 0;
  738. void            regdump();
  739. STATIC char    *regprop();
  740. #endif
  741.  
  742. /*
  743.  - regexec - match a regexp against a string
  744.  */
  745. int
  746. regexec(prog, string, at_bol)
  747.     register regexp *prog;
  748.     register char  *string;
  749.     int             at_bol;
  750. {
  751.     register char  *s;
  752.     extern char    *cstrchr();
  753.  
  754.     /* Be paranoid... */
  755.     if (prog == NULL || string == NULL) {
  756.     regerror("NULL parameter");
  757.     return (0);
  758.     }
  759.     /* Check validity of program. */
  760.     if (UCHARAT(prog->program) != MAGIC) {
  761.     regerror("corrupted program");
  762.     return (0);
  763.     }
  764.     /* If there is a "must appear" string, look for it. */
  765.     if (prog->regmust != NULL) {
  766.     s = string;
  767.     while ((s = cstrchr(s, prog->regmust[0])) != NULL) {
  768.         if (cstrncmp(s, prog->regmust, prog->regmlen) == 0)
  769.         break;        /* Found it. */
  770.         s++;
  771.     }
  772.     if (s == NULL)        /* Not present. */
  773.         return (0);
  774.     }
  775.     /* Mark beginning of line for ^ . */
  776.     if (at_bol)
  777.     regbol = string;    /* is possible to match bol */
  778.     else
  779.     regbol = NULL;        /* we aren't there, so don't match it */
  780.  
  781.     /* Simplest case:  anchored match need be tried only once. */
  782.     if (prog->reganch)
  783.     return (regtry(prog, string));
  784.  
  785.     /* Messy cases:  unanchored match. */
  786.     s = string;
  787.     if (prog->regstart != '\0')
  788.     /* We know what char it must start with. */
  789.     while ((s = cstrchr(s, prog->regstart)) != NULL) {
  790.         if (regtry(prog, s))
  791.         return (1);
  792.         s++;
  793.     }
  794.     else
  795.     /* We don't -- general case. */
  796.     do {
  797.         if (regtry(prog, s))
  798.         return (1);
  799.     } while (*s++ != '\0');
  800.  
  801.     /* Failure. */
  802.     return (0);
  803. }
  804.  
  805. /*
  806.  - regtry - try match at specific point
  807.  */
  808. static int            /* 0 failure, 1 success */
  809. regtry(prog, string)
  810.     regexp         *prog;
  811.     char           *string;
  812. {
  813.     register int    i;
  814.     register char **sp;
  815.     register char **ep;
  816.  
  817.     reginput = string;
  818.     regstartp = prog->startp;
  819.     regendp = prog->endp;
  820.  
  821.     sp = prog->startp;
  822.     ep = prog->endp;
  823.     for (i = NSUBEXP; i > 0; i--) {
  824.     *sp++ = NULL;
  825.     *ep++ = NULL;
  826.     }
  827.     if (regmatch(prog->program + 1)) {
  828.     prog->startp[0] = string;
  829.     prog->endp[0] = reginput;
  830.     return (1);
  831.     } else
  832.     return (0);
  833. }
  834.  
  835. /*
  836.  - regmatch - main matching routine
  837.  *
  838.  * Conceptually the strategy is simple:  check to see whether the current
  839.  * node matches, call self recursively to see whether the rest matches,
  840.  * and then act accordingly.  In practice we make some effort to avoid
  841.  * recursion, in particular by going through "ordinary" nodes (that don't
  842.  * need to know whether the rest of the match failed) by a loop instead of
  843.  * by recursion.
  844.  */
  845. static int            /* 0 failure, 1 success */
  846. regmatch(prog)
  847.     char           *prog;
  848. {
  849.     register char  *scan;    /* Current node. */
  850.     char           *next;    /* Next node. */
  851.     extern char    *strchr();
  852.  
  853.     scan = prog;
  854. #ifdef DEBUG
  855.     if (scan != NULL && regnarrate)
  856.     fprintf(stderr, "%s(\n", regprop(scan));
  857. #endif
  858.     while (scan != NULL) {
  859. #ifdef DEBUG
  860.     if (regnarrate)
  861.         fprintf(stderr, "%s...\n", regprop(scan));
  862. #endif
  863.     next = regnext(scan);
  864.  
  865.     switch (OP(scan)) {
  866.       case BOL:
  867.         if (reginput != regbol)
  868.         return (0);
  869.         break;
  870.       case EOL:
  871.         if (*reginput != '\0')
  872.         return (0);
  873.         break;
  874.       case ANY:
  875.         if (*reginput == '\0')
  876.         return (0);
  877.         reginput++;
  878.         break;
  879.       case EXACTLY:{
  880.         register int    len;
  881.         register char  *opnd;
  882.  
  883.         opnd = OPERAND(scan);
  884.         /* Inline the first character, for speed. */
  885.         if (mkup(*opnd) != mkup(*reginput))
  886.             return (0);
  887.         len = strlen(opnd);
  888.         if (len > 1 && cstrncmp(opnd, reginput, len) != 0)
  889.             return (0);
  890.         reginput += len;
  891.         }
  892.         break;
  893.       case ANYOF:
  894.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  895.         return (0);
  896.         reginput++;
  897.         break;
  898.       case ANYBUT:
  899.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  900.         return (0);
  901.         reginput++;
  902.         break;
  903.       case NOTHING:
  904.         break;
  905.       case BACK:
  906.         break;
  907.       case OPEN + 1:
  908.       case OPEN + 2:
  909.       case OPEN + 3:
  910.       case OPEN + 4:
  911.       case OPEN + 5:
  912.       case OPEN + 6:
  913.       case OPEN + 7:
  914.       case OPEN + 8:
  915.       case OPEN + 9:{
  916.         register int    no;
  917.         register char  *save;
  918.  
  919.         no = OP(scan) - OPEN;
  920.         save = reginput;
  921.  
  922.         if (regmatch(next)) {
  923.             /*
  924.              * Don't set startp if some later invocation of the same
  925.              * parentheses already has. 
  926.              */
  927.             if (regstartp[no] == NULL)
  928.             regstartp[no] = save;
  929.             return (1);
  930.         } else
  931.             return (0);
  932.         }
  933.         /* break; Not Reached */
  934.       case CLOSE + 1:
  935.       case CLOSE + 2:
  936.       case CLOSE + 3:
  937.       case CLOSE + 4:
  938.       case CLOSE + 5:
  939.       case CLOSE + 6:
  940.       case CLOSE + 7:
  941.       case CLOSE + 8:
  942.       case CLOSE + 9:{
  943.         register int    no;
  944.         register char  *save;
  945.  
  946.         no = OP(scan) - CLOSE;
  947.         save = reginput;
  948.  
  949.         if (regmatch(next)) {
  950.             /*
  951.              * Don't set endp if some later invocation of the same
  952.              * parentheses already has. 
  953.              */
  954.             if (regendp[no] == NULL)
  955.             regendp[no] = save;
  956.             return (1);
  957.         } else
  958.             return (0);
  959.         }
  960.         /* break; Not Reached */
  961.       case BRANCH:{
  962.         register char  *save;
  963.  
  964.         if (OP(next) != BRANCH)    /* No choice. */
  965.             next = OPERAND(scan);    /* Avoid recursion. */
  966.         else {
  967.             do {
  968.             save = reginput;
  969.             if (regmatch(OPERAND(scan)))
  970.                 return (1);
  971.             reginput = save;
  972.             scan = regnext(scan);
  973.             } while (scan != NULL && OP(scan) == BRANCH);
  974.             return (0);
  975.             /* NOTREACHED */
  976.         }
  977.         }
  978.         break;
  979.       case STAR:
  980.       case PLUS:{
  981.         register char   nextch;
  982.         register int    no;
  983.         register char  *save;
  984.         register int    min;
  985.  
  986.         /*
  987.          * Lookahead to avoid useless match attempts when we know
  988.          * what character comes next. 
  989.          */
  990.         nextch = '\0';
  991.         if (OP(next) == EXACTLY)
  992.             nextch = *OPERAND(next);
  993.         min = (OP(scan) == STAR) ? 0 : 1;
  994.         save = reginput;
  995.         no = regrepeat(OPERAND(scan));
  996.         while (no >= min) {
  997.             /* If it could work, try it. */
  998.             if (nextch == '\0' || *reginput == nextch)
  999.             if (regmatch(next))
  1000.                 return (1);
  1001.             /* Couldn't or didn't -- back up. */
  1002.             no--;
  1003.             reginput = save + no;
  1004.         }
  1005.         return (0);
  1006.         }
  1007.         /* break; Not Reached */
  1008.       case END:
  1009.         return (1);        /* Success! */
  1010.         /* break; Not Reached */
  1011.       default:
  1012.         regerror("memory corruption");
  1013.         return (0);
  1014.         /* break; Not Reached */
  1015.     }
  1016.  
  1017.     scan = next;
  1018.     }
  1019.  
  1020.     /*
  1021.      * We get here only if there's trouble -- normally "case END" is the
  1022.      * terminating point. 
  1023.      */
  1024.     regerror("corrupted pointers");
  1025.     return (0);
  1026. }
  1027.  
  1028. /*
  1029.  - regrepeat - repeatedly match something simple, report how many
  1030.  */
  1031. static int
  1032. regrepeat(p)
  1033.     char           *p;
  1034. {
  1035.     register int    count = 0;
  1036.     register char  *scan;
  1037.     register char  *opnd;
  1038.  
  1039.     scan = reginput;
  1040.     opnd = OPERAND(p);
  1041.     switch (OP(p)) {
  1042.       case ANY:
  1043.     count = strlen(scan);
  1044.     scan += count;
  1045.     break;
  1046.       case EXACTLY:
  1047.     while (mkup(*opnd) == mkup(*scan)) {
  1048.         count++;
  1049.         scan++;
  1050.     }
  1051.     break;
  1052.       case ANYOF:
  1053.     while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1054.         count++;
  1055.         scan++;
  1056.     }
  1057.     break;
  1058.       case ANYBUT:
  1059.     while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1060.         count++;
  1061.         scan++;
  1062.     }
  1063.     break;
  1064.       default:            /* Oh dear.  Called inappropriately. */
  1065.     regerror("internal foulup");
  1066.     count = 0;        /* Best compromise. */
  1067.     break;
  1068.     }
  1069.     reginput = scan;
  1070.  
  1071.     return (count);
  1072. }
  1073.  
  1074. /*
  1075.  - regnext - dig the "next" pointer out of a node
  1076.  */
  1077. static char    *
  1078. regnext(p)
  1079.     register char  *p;
  1080. {
  1081.     register int    offset;
  1082.  
  1083.     if (p == ®dummy)
  1084.     return (NULL);
  1085.  
  1086.     offset = NEXT(p);
  1087.     if (offset == 0)
  1088.     return (NULL);
  1089.  
  1090.     if (OP(p) == BACK)
  1091.     return (p - offset);
  1092.     else
  1093.     return (p + offset);
  1094. }
  1095.  
  1096. #ifdef DEBUG
  1097.  
  1098. STATIC char    *regprop();
  1099.  
  1100. /*
  1101.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1102.  */
  1103. void
  1104. regdump(r)
  1105.     regexp         *r;
  1106. {
  1107.     register char  *s;
  1108.     register char   op = EXACTLY;    /* Arbitrary non-END op. */
  1109.     register char  *next;
  1110.     extern char    *strchr();
  1111.  
  1112.  
  1113.     s = r->program + 1;
  1114.     while (op != END) {        /* While that wasn't END last time... */
  1115.     op = OP(s);
  1116.     printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
  1117.     next = regnext(s);
  1118.     if (next == NULL)    /* Next ptr. */
  1119.         printf("(0)");
  1120.     else
  1121.         printf("(%d)", (s - r->program) + (next - s));
  1122.     s += 3;
  1123.     if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1124.         /* Literal string, where present. */
  1125.         while (*s != '\0') {
  1126.         putchar(*s);
  1127.         s++;
  1128.         }
  1129.         s++;
  1130.     }
  1131.     putchar('\n');
  1132.     }
  1133.  
  1134.     /* Header fields of interest. */
  1135.     if (r->regstart != '\0')
  1136.     printf("start `%c' ", r->regstart);
  1137.     if (r->reganch)
  1138.     printf("anchored ");
  1139.     if (r->regmust != NULL)
  1140.     printf("must have \"%s\"", r->regmust);
  1141.     printf("\n");
  1142. }
  1143.  
  1144. /*
  1145.  - regprop - printable representation of opcode
  1146.  */
  1147. static char    *
  1148. regprop(op)
  1149.     char           *op;
  1150. {
  1151.     register char  *p;
  1152.     static char     buf[50];
  1153.  
  1154.     (void) strcpy(buf, ":");
  1155.  
  1156.     switch (OP(op)) {
  1157.       case BOL:
  1158.     p = "BOL";
  1159.     break;
  1160.       case EOL:
  1161.     p = "EOL";
  1162.     break;
  1163.       case ANY:
  1164.     p = "ANY";
  1165.     break;
  1166.       case ANYOF:
  1167.     p = "ANYOF";
  1168.     break;
  1169.       case ANYBUT:
  1170.     p = "ANYBUT";
  1171.     break;
  1172.       case BRANCH:
  1173.     p = "BRANCH";
  1174.     break;
  1175.       case EXACTLY:
  1176.     p = "EXACTLY";
  1177.     break;
  1178.       case NOTHING:
  1179.     p = "NOTHING";
  1180.     break;
  1181.       case BACK:
  1182.     p = "BACK";
  1183.     break;
  1184.       case END:
  1185.     p = "END";
  1186.     break;
  1187.       case OPEN + 1:
  1188.       case OPEN + 2:
  1189.       case OPEN + 3:
  1190.       case OPEN + 4:
  1191.       case OPEN + 5:
  1192.       case OPEN + 6:
  1193.       case OPEN + 7:
  1194.       case OPEN + 8:
  1195.       case OPEN + 9:
  1196.     sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
  1197.     p = NULL;
  1198.     break;
  1199.       case CLOSE + 1:
  1200.       case CLOSE + 2:
  1201.       case CLOSE + 3:
  1202.       case CLOSE + 4:
  1203.       case CLOSE + 5:
  1204.       case CLOSE + 6:
  1205.       case CLOSE + 7:
  1206.       case CLOSE + 8:
  1207.       case CLOSE + 9:
  1208.     sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
  1209.     p = NULL;
  1210.     break;
  1211.       case STAR:
  1212.     p = "STAR";
  1213.     break;
  1214.       case PLUS:
  1215.     p = "PLUS";
  1216.     break;
  1217.       default:
  1218.     regerror("corrupted opcode");
  1219.     break;
  1220.     }
  1221.     if (p != NULL)
  1222.     (void) strcat(buf, p);
  1223.     return (buf);
  1224. }
  1225. #endif
  1226.  
  1227. /*
  1228.  * The following is provided for those people who do not have strcspn() in
  1229.  * their C libraries.  They should get off their butts and do something
  1230.  * about it; at least one public-domain implementation of those (highly
  1231.  * useful) string routines has been published on Usenet.
  1232.  */
  1233. #ifdef STRCSPN
  1234. /*
  1235.  * strcspn - find length of initial segment of s1 consisting entirely
  1236.  * of characters not from s2
  1237.  */
  1238.  
  1239. static int
  1240. strcspn(s1, s2)
  1241.     char           *s1;
  1242.     char           *s2;
  1243. {
  1244.     register char  *scan1;
  1245.     register char  *scan2;
  1246.     register int    count;
  1247.  
  1248.     count = 0;
  1249.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1250.     for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1251.         if (*scan1 == *scan2++)
  1252.         return (count);
  1253.     count++;
  1254.     }
  1255.     return (count);
  1256. }
  1257. #endif
  1258.  
  1259. int
  1260. cstrncmp(s1, s2, n)
  1261.     char           *s1, *s2;
  1262.     int             n;
  1263. {
  1264.     char           *p, *S1, *S2, *strsave();
  1265.     int             rval;
  1266.  
  1267.     if (!reg_ic)
  1268.     return (strncmp(s1, s2, n));
  1269.  
  1270.     S1 = strsave(s1);
  1271.     S2 = strsave(s2);
  1272.  
  1273.     for (p = S1; *p; p++)
  1274.     if (islower(*p))
  1275.         *p = toupper(*p);
  1276.  
  1277.     for (p = S2; *p; p++)
  1278.     if (islower(*p))
  1279.         *p = toupper(*p);
  1280.  
  1281.     rval = strncmp(S1, S2, n);
  1282.  
  1283.     free(S1);
  1284.     free(S2);
  1285.  
  1286.     return rval;
  1287. }
  1288.  
  1289. char           *
  1290. cstrchr(s, c)
  1291.     char           *s;
  1292.     char            c;
  1293. {
  1294.     char           *p;
  1295.  
  1296.     for (p = s; *p; p++) {
  1297.     if (mkup(*p) == mkup(c))
  1298.         return p;
  1299.     }
  1300.     return NULL;
  1301. }
  1302.